"""
Problem 96: https://projecteuler.net/problem=96

a popular puzzle concept. Its origin is unclear, but credit
must be attributed to Leonhard Euler who invented a similar,
and much more difficult, puzzle idea called Latin Squares.
The objective of Su Doku puzzles, however, is to replace the
blanks (or zeros) in a 9 by 9 grid in such that each row,
column, and 3 by 3 box contains each of the digits 1 to 9.
Below is an example of a typical starting puzzle grid and
its solution grid.

  0 0 3 | 0 2 0 | 6 0 0      4 8 3 | 9 2 1 | 6 5 7
  9 0 0 | 3 0 5 | 0 0 1      9 6 7 | 3 4 5 | 8 2 1
  0 0 1 | 8 0 6 | 4 0 0      2 5 1 | 8 7 6 | 4 9 3
  ---------------------      ---------------------
  0 0 8 | 1 0 2 | 9 0 0      5 4 8 | 1 3 2 | 9 7 6
  7 0 0 | 0 0 0 | 0 0 8      7 2 9 | 5 6 4 | 1 3 8
  0 0 6 | 7 0 8 | 2 0 0      1 3 6 | 7 9 8 | 2 4 5
  ---------------------      ---------------------
  0 0 2 | 6 0 9 | 5 0 0      3 7 2 | 6 8 9 | 5 1 4
  8 0 0 | 2 0 3 | 0 0 9      8 1 4 | 2 5 3 | 7 6 9
  0 0 5 | 0 1 0 | 3 0 0      6 9 5 | 4 1 7 | 3 8 2

A well constructed Su Doku puzzle has a unique solution and can
be solved by logic, although it may be necessary to employ "guess
and test" methods in order to eliminate options (there is much
contested opinion over this). The complexity of the search
determines the difficulty of the puzzle; the example above is
considered easy because it can be solved by straight forward
direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target
As...'), contains fifty different Su Doku puzzles ranging in
difficulty, but all with unique solutions (the first puzzle
in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit
numbers found in the top left corner of each solution grid;
for example, 483 is the 3-digit number found in the top left
corner of the solution grid above.
"""
from copy import deepcopy


Sudokus = '['
SudokusFile = 'p096_sudoku.txt'
with open(SudokusFile, 'r') as fp:
    for line in fp:
        if 'Grid' in line:
            line = '],['
        tmp = '"'+line.strip() + '",'
        Sudokus += tmp

Sudokus = Sudokus.replace('["],', '[')
Sudokus = Sudokus.replace('[",', '[')
Sudokus = Sudokus.replace(',"]', ']')
Sudokus = eval(Sudokus[:-1] + ']]')
# print(Sudokus[0])

##########################  clearup  ######################


def cleanup_ij(sudo, i, j):
    sureNum = sudo[i][j]

    # row
    for m in range(9):
        if m == j:
            continue
        try:
            sudo[i][m].remove(sureNum)
        except:
            pass

        if not sudo[i][m]:
            sudo = None
            return

    # col
    for m in range(9):
        if m == i:
            continue
        try:
            sudo[m][j].remove(sureNum)
        except:
            pass

        if not sudo[m][j]:
            sudo = None
            return

    # block
    for bi in range(i//3*3, i//3*3+3):
        for bj in range(j//3*3, j//3*3+3):
            if i == bi and j == bj:
                continue
            try:
                sudo[bi][bj].remove(sureNum)
            except:
                pass

        if not sudo[bi][bj]:
            sudo = None
            return


def cleanup_list_ij(sudo):
    while True:
        if sudo is None:
            return

        newSureNums = [(i, j) for i in range(9) for j in range(9)
                       if isinstance(sudo[i][j], list) and len(sudo[i][j]) == 1]
        if newSureNums:
            for i, j in newSureNums:
                try:
                    # sudo[i][j] is []
                    sudo[i][j] = sudo[i][j][0]
                except:
                    sudo = None
                    return
                cleanup_ij(sudo, i, j)
        else:
            return

##########################  guess  ######################


def findtryPos(sudo):
    '''
    find [x,y]
    '''

    lens = 9
    ti, tj = None, None
    for i in range(9):
        for j in range(9):
            tmp = len(sudo[i][j])
            if tmp == 2:
                return i, j
            if lens > tmp > 2:
                lens, ti, tj = tmp, i, j
    return ti, tj


def guessAnswer(sudo):
    '''
    guess
    '''
    Answer = None
    
    def search(sd):
        nonlocal Answer

        if isFinish(sd):
            Answer = sd
            return

        if isFailure(sd):
            return
    
        i, j = findtryPos(sd)

        # print('try', sd[i][j])
        for cand in sd[i][j]:
            trySudo = deepcopy(sd)
            trySudo[i][j] = cand
            cleanup_ij(trySudo, i, j)
            cleanup_list_ij(trySudo)

            # pprint(trySudo)
            # print('-'*81)

            if isFailure(trySudo):
                continue

            if isFinish(trySudo):
                Answer = trySudo
                return
            else:
                search(trySudo)

    search(sudo)

    return Answer

##########################  finished or failure  ########


def isFinish(sudo):
    if sudo == None:
        return False

    for i in range(9):
        for j in range(9):
            if not isinstance(sudo[i][j], str):
                return False
    return True


def isFailure(sudo):
    if sudo is None:
        return True

    for i in range(9):
        for j in range(9):
            if not sudo[i][j]:
                sudo = None
                return True
    return False

##########################  print  ######################


def pprint(sudo):

    if sudo == None:
        return

    for i in range(9):
        for j in range(9):
            print(''.join(sudo[i][j]).ljust(9), end=' ')
        print()


##########################  finished or failure  ########
def puzzle(sudo):

    sudo = [list(line) for line in sudo]
    for i in range(9):
        for j in range(9):
            if sudo[i][j] == '0':
                sudo[i][j] = list(map(str, range(1, 10)))

    return sudo


def solve(sudo):
    sudo = puzzle(sudo)

    for i in range(9):
        for j in range(9):
            if isinstance(sudo[i][j], str):
                cleanup_ij(sudo, i, j)

    cleanup_list_ij(sudo)

    if sudo is None:
        return

    if isFinish(sudo):
        return sudo

    # guess
    return guessAnswer(sudo)


def solution() -> int:
    res = 0

    for i in range(len(Sudokus)):
        ans = solve(Sudokus[i])
        print(i+1, '-'*81)
        if ans == None:
            print(i+1, 'fail!')
            continue
        else:
            pprint(ans)
            res += int(''.join(ans[0][j] for j in range(3)))
    
    return res



if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 24702
